The present invention relates generally to the field of communication network design, and more particularly to a method for partitioning traffic and placing add/drop multiplexers in a stacked ring network.
Modern digital telecommunication systems are built upon a network consisting of a plurality of nodes or cites that are interconnected by spans or transmissions facilities. A primary goal of telecommunications network design is to serve the demand in capacity between the nodes at the least cost, while maintaining an acceptable level of survivability in the event of failures. Two elements of cost in a network are transmission costs and equipment costs. Transmission cost is generally based upon the transmission distance. Equipment cost includes the cost of add/drop multiplexers, as well as the cost of other equipment.
Recently, there has been a move away from mesh topology for telecommunications networks toward a ring topology. In a bidirectional line switched ring, the demands on the ring are allowed to be routed on either side of the ring, and the capacity for all spans of the ring is required to be the same.
A ring topology offers advantages over a mesh topology, primarily in that a ring is self healing and therefore may be restored in a matter of milliseconds after a failure. However, if the routing of traffic is not done properly, then there can be large amounts of capacity not utilized and the total capacity deployed on the ring can be significantly higher than what is really required. It is therefore a problem to load traffic on a bidirectional line switched ring so that the number of ring layers can be minimized.
The traffic loading problem has two components. The first component is defined as the minimum capacity required for the ring. The second requirement is defined as an integer multiflow that satisfies both capacity and demand constraints. In application Ser. No. 09/036,392, filed Mar. 6, 1998, titled Method for Optimal Routing in a Bi-Directional Line Switched SONET Ring, the disclosure of which is incorporated herein by reference, there is disclosed a method of assigning capacity in routing flow in a SONET ring based upon topology and demand data.
Due to the fixed modularity in SONET transmission system, if the required capacity of the ring exceeds the modularity limit (e.g., OC48 or OC192), then demands on the ring need to be separated into several ring layers. The layering of demands and assignment of flow on overlapping ring layers presents several complicated optimization problems. One problem is to decompose the demands on to the several layers so that the number of ring layers required is minimized. Another problem is to layer the demand and assign the flow so that the total number of add/drop multiplexers (ADMs) can be minimized. The ADM problem is further complicated by the fact that an order for demand from a point A to a point B to traverse between ring layers 1 and 2 at an intermediate point C, ADMs need to be placed on both layers 1 and 2. A further problem is in minimizing the number of demands that traverse between different ring layers in order to ease network management.
The foregoing problems are further complicated if there is no internal time slot interchange function in the ADMs of the ring, which means that one unit of demand from point A to point B will need to be assigned to the same time slot on each intermediate span. In order to change time slot assignment at an intermediate point C, the unit of demand must be dropped from the originally assigned time slot at point C onto a digital cross connect and then reinserted in a new time slot at point C again. The drop and reinsert scenario should be minimized. Finally, in order to accommodate future growth, it is desirable that the time slot assignment be done so that the unused time slots in the ring are in contiguous locations.
Finding a single optimal solution to the above problems is a difficult task. To solve the combined problem of flow layering, ADM placement, and time slot assignment, is even more complicated since the different objectives mentioned above are often conflicting. Most heuristics attempt to address only a single objective, and do not provide a solution that is satisfactory in terms of achieving some guaranteed worst case bound. Because of the importance of this combined problem, a new method and system is needed to address the objectives by minimizing the number of rings and the number of ADMs.
The present invention provides a method for partitioning traffic and placing add/drop multiplexers in a stacked ring network. The method of the present invention determines the number of ring layers necessary to support the traffic and divides the ring layers into a first set of layers and a second set of layers. The method then determines the interchange points between the first set of layers and the second set of layers and allocates the traffic between the first set of layers and the second set of layers. The method subdivides each of the first and second sets of layers into a first set of layers and a second set of layers, and repeats the process of determining interchange points, allocating traffic, and subdividing the sets of layers for each set of layers until each set of layers consists of one layer.
The number of ring layers necessary to support the traffic is equal to the ceiling of the capacity required to support the traffic divided by the modularity of the ring. The capacity of the first set of layers is equal to the ceiling of half the number of layers multiplied by the modularity of the ring. The capacity of the second set of layers is equal to the floor of half the number of layers multiplied by the modularity of the ring. The method of the present invention determines the interchange points between the first set of layers and the second set of layers by determining, for each node of the ring, if the traffic terminating at that node is greater than the capacity of the first set of layers.
The method places one add/drop multiplexer on each set of layers at each interchange point. The method places one add/drop multiplexer on only the first set of layers at each terminating node of the ring determined not to be an interchange point. The method allocates traffic between the first set of layers and the second set of layers by assigning traffic terminating at each node determined not to be an interchange point to the first set of layers. The method assigns traffic terminating at each interchange point to the second set of layers until the capacity of the second set of layers is exhausted and then assigns the remaining traffic terminating at each interchange point to the first set of layers.